#include "stdafx.h"
#include "sort.h"


void BubbleSort(int *data, int size){
	int tmp = 0;
	bool flag;
	for(int i = 1; i < size; i++){
		flag = false;
		for(int j = size - 1; j >= i; j--)
			if(data[j] < data[j - 1]){
				tmp = data[j];
				data[j] = data[j - 1];
				data[j - 1] = tmp;
				flag = true;
			}
		if(!flag)
		return;
	}
}

void InsertSort(int *data, int size){
	int tmp,pos;
	for(int i = 1; i < size; i++){
		tmp = data[i];
		pos = i - 1;
		while((pos >= 0) && (tmp < data[pos])){
			data[pos + 1] = data[pos];
			pos--;
		}
		data[pos + 1] = tmp;
	}
}

int Partition(int *data, int low, int high){
	int tmp = data[low];
	while(low < high){
		while(low < high && data[high] >= tmp)
			--high;
		data[low] = data[high];
		while(low < high && data[low] <= tmp)
			++low;
		data[high] = data[low];
	}
	data[low] = tmp;
	return low;
}

void QSort(int *data,int low, int high){
	if(low < high){
		int key = Partition(data,low,high);
		QSort(data,low, key - 1);
		QSort(data,key + 1, high);
	}
}

void QuickSort(int *data, int size){
	QSort(data,0,size -1);
}

// a i->m, m+1->n - b
void Merge(int *a, int *b, int i, int m, int n){
	int j , k;
	for(j = m + 1, k = i; j <= n && i <= m; k++){
		if(a[i] < a[j])
			b[k] = a[i++];
		else
			b[k] = a[j++];
	}
	if(j <= n)
		for(; j <= n; j++)
			b[k++] = a[j];
	if(i <= m)
		for(; i <= m; i++)
			b[k++] = a[i];
}

void MSort(int *a, int *b, int s, int t){
	int m;
	int c[100];
	if(s == t)
		b[s] = a[s];
	else{
		m = (s + t)/2;
		MSort(a,c,s,m);
		MSort(a,c,m+1,t);
		Merge(c,b,s,m,t);
	}
}

void MergeSort( int *a, int size){
	MSort(a,a,0,size - 1);
}

void MergeArrays(int *a, int *b, int *c, int size_a, int size_b){
	int p1 = size_a - 1;
	int p2 = size_b - 1;
	int p3 = size_a + size_b - 1;
	while( p1 >= 0 && p2 >= 0){
		if(a[p1] < b[p2])
			c[p3--] = b[p2--];
		else
			c[p3--] = a[p1--];
	}
	if( p1 >= 0)
		for(; p1 >= 0; p1--)
			c[p3--] = a[p1];
	if( p2 >= 0)
		for(; p2 >= 0; p2--)
			c[p3--] = b[p2];
}


